// 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

// 说明：
// 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

// 示例 1:

// 输入: root = [3,1,4,null,2], k = 1
//    3
//   / \
//  1   4
//   \
//    2
// 输出: 1
// 示例 2:

// 输入: root = [5,3,6,2,4,null,null,1], k = 3
//        5
//       / \
//      3   6
//     / \
//    2   4
//   /
//  1
// 输出: 3
// 进阶：
// 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> nums{};
        inOrder(root, nums); // 中序遍历二叉搜索树的结果是从小到大排好序的
        return nums[k-1];
    }
    void inOrder(TreeNode* node, vector<int>& nums) {
        if (!node) return;
        if (node->left) inOrder(node->left, nums);
        nums.push_back(node->val);
        if (node->right) inOrder(node->right, nums);
    }
};

// 中序遍历，迭代，用栈
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st{};
        while (root) {
            st.push(root);
            root = root->left;
        }
        while (k) {
            TreeNode* node = st.top();
            st.pop();
            k--;
            if (k == 0) return node->val;
            if (node->right) {
                node = node->right;
                while (node) {
                    st.push(node);
                    node = node->left;
                }
            }
        }
        return 0;
    }
};